package 链表题目.链表内指定区间反转;

/**
 * 解法1 双指针法
 */
public class Solution1 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        // 定义一个虚拟头节点
        ListNode tmpHead = new ListNode(-1);
        tmpHead.next = head;

        // 1. 找到left左边的节点;
        ListNode pre = tmpHead;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }

        // 2.找到right处节点
        ListNode right = pre;
        for (int i = 0; i < n - m + 1; i++) {
            right = right.next;
        }

        // 3.记录 m - n的节点
        ListNode leftNode = pre.next;
        ListNode cur = right.next;

        // 4.断开原来链表
        pre.next = null;
        right.next = null;

        // 5.翻转子链表
        // reverseChild(leftNode);
        // pre.next = right;
        // leftNode.next = cur;

        ListNode newList = reverseChild(leftNode);
        pre.next = right;
        newList.next = cur;

        return tmpHead.next;
    }

    // 逆置单链表
    public ListNode reverseChild(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return head;
    }
}
